

package main.new_2024.month_06;


import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Description: todo 735. 小行星碰撞
 * 给定一个整数数组 asteroids，表示在同一行的小行星。
 * 对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
 * 找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。
 *
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0613 {


    //小行星碰撞
    public int[] asteroidCollision(int[] asteroids) {
        //先入后出保存
        Deque<Integer> stack = new ArrayDeque<>();
        for (int aster:asteroids){
            boolean alive = true;
            while (alive && aster < 0 && !stack.isEmpty() && stack.peek() > 0) {
                alive = stack.peek() < -aster; // aster 是否存在
                if (stack.peek() <= -aster) {  // 栈顶行星爆炸
                    stack.pop();
                }
            }
            if (alive) {
                stack.push(aster);
            }
        }
        if (!stack.isEmpty()){
            int[] result = new int[stack.size()];
            for (int i = stack.size()-1 ; i>=0;i--){
                result[i] = stack.pop();
            }
            return result;
        }else {
            return new int[0];
        }

    }

    public static void main(String[] args) {
        Solution0613 test = new Solution0613();
        int[] asteroids = {3,2,-1,1};
        int[] ints = test.asteroidCollision(asteroids);
        System.out.println(ints);
    }

}

